The present invention pertains to implementation of a method for fast image compression and expansion in a Single Instruction-Multiple Datastream (SIMD) array processor, and provides real-time spatial resolution image compression and expansion processing.
Spatial resolution compression and expansion are necessary in multiresolution image processing. Existing methods for image compression and expansion require too many instructions, and may not be suitable for certain types of real-time applications.
For the purpose of this discussion, the terms compression and expansion have the following meanings. Compression means sub-sampling or reducing the spatial resolution of the given image by a factor K, where K is some small positive integer. It is equivalent to low-pass filtering. Expansion means magnifying or increasing the size of the given image by a factor K. For convenience, the methods will be explained using an example with K=2. Let I(m,n) be the original image containing 2M.times.2N pixels, where m=1, 2, . . . , 2M; n=1, 2, . . . 2N; M and N are positive integers. The compression of I(m,n) by a factor of 2 in both dimensions of the image yields EQU C(j,k)=I(2j,2k)
where C(j,k) is the compressed image; j=1, 2, . . . , M; and k=1, 2, . . . , N. Some applications may require local averaging to be performed on I(m,n) prior to the compression.
There are varying methods for achieving expansion or compression. One type of method is a sequential method; another is a parallel method such as can be implemented on a parallel processor. The complexity of a sequential method may be expressed as O(M.times.N), on the order of magnitude of M.times.N or proportional to M.times.N. The sequential method involves the copying of M.times.N selected pixels, one pixel at a time, from I(2j,2k) to C(j,k). Using a parallel method, however, image compression is performed in two stages; first, with respect to rows, and then with respect to columns. To compress the rows, image I(2j,2k) is shifted until row 2j of image I(2j,2k) aligns with row j of compressed image C(j,k) before all pixels in row 2j are copied simultaneously into compressed image C(j,k), as shown in FIGS. 12(a)-(q) for M=16. After all selected M rows are copied, a similar process is applied to the columns. The complexity of such a parallel method may thus be expressed as O(M+N). The total number of GAPP instructions (clock cycles) required by this method for compressing a 108.times.384 pixel image, 8 bits per pixel, down to a 54.times.192 pixel image, 8 bits per pixel, is 20,316.
General mathematical properties of image compression and other digital image processing techniques are presented, for example, in Digital Image Processing (Addison-Wesley, 1992) by R. Gonzalez and R. Woods, and in "The Manipulation of Raster-based Topographic Data on a Parallel Processor," Proceedings of IEEE Computer Society Conference on Pattern Recognition and Image Processing, PRIP-82, pp. 396-404, by T. A. Adams and K. A. Smith.
The parallel method is an example of certain data processing tasks that require that substantially identical logical or arithmetical operations be performed on large amounts of data. One approach to carrying out such tasks which is drawing increasing attention is massively parallel processing. In parallel processing, each element or cell of an array processor made up of such cells processes its own bit of data at the same time as all other cells of the array processor perform the same process on their own bit of data. Such machines are referred to by several names, including Single Instruction-Multiple Datastream (SIMD), and massively parallel array processors.
A common arrangement for such a machine is as a rectangular array of cells, with each interior cell connected to its four nearest neighboring cells and each edge cell connected to a data input/output device. Each cell is connected as well to a master controller which coordinates the movement of data through the array by providing appropriate instructions to the processing elements. When used in high resolution image processing, such processors handle the image pixels as a data matrix which can be loaded into and processed quickly and efficiently by the processor array.
Although based upon the same generic concept of an array of cells all performing the same function in unison, parallel processors vary in details of cell interconnection and design. For example, U.S. Pat. No. 4,215,401 to Holsztynski et al. discloses a cell which includes a random access memory (RAM), a single bit accumulator, and a simple logical gate. The disclosed cell is extremely simple and, hence, inexpensive and easily fabricated. A negative consequence of this simplicity, however, is that some complex computational operations are quite cumbersome so that it may require many basic operations (instructions) to perform a complex task.
U.S. Pat. No. 4,739,474, to Holsztynski et al., represents a higher level of cell complexity, in which the logic gate is replaced by a full adder capable of performing both arithmetic and logical functions. Pressing the full adder into dual service creates an efficiency which more than offsets the added complexity and cost incurred by including a full adder in each cell.
Parallel processors may also vary in the manner of cell interconnection. As mentioned above, cells are typically connected to their nearest physical neighbors. All cells except those at the edge of the entire array are connected to four neighbors. Significant benefits may, however, flow from providing for alternate paths of interconnection and, specifically, in providing programmable, flexible interconnection between cells.